package leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * Created by 林剑 on 2016/10/8.
 */
public class leetcode46 {
    /*public List<List<Integer>> permute(int[] num) {
        ArrayList<List<Integer>> result = new ArrayList<List<Integer>>();

        //start from an empty list
        result.add(new ArrayList<Integer>());

        for (int i = 0; i < num.length; i++) {
            //list of list in current iteration of the array num
            ArrayList<ArrayList<Integer>> current = new ArrayList<ArrayList<Integer>>();

            for (List<Integer> l : result) {
                // # of locations to insert is largest index + 1
                for (int j = 0; j < l.size()+1; j++) {
                    // + add num[i] to different locations
                    l.add(j, num[i]);

                    ArrayList<Integer> temp = new ArrayList<Integer>(l);
                    current.add(temp);

                    //System.out.println(temp);

                    // - remove num[i] add
                    l.remove(j);
                }
            }

            result = new ArrayList<List<Integer>>(current);
        }

        return result;
    }*/


    public List<List<Integer>> permute(int[] num) {
        ArrayList<List<Integer>> res = new ArrayList<List<Integer>>();
        ArrayList<Integer> item = new ArrayList<Integer>();

        if(num.length==0||num==null)
            return res;
        boolean[] visited = new boolean[num.length];

        permutation_helper(num,res,item,visited);
        return res;
    }

    public void permutation_helper(int[] num, ArrayList<List<Integer>> res, ArrayList<Integer> item,boolean[] visited){
        if(item.size()==num.length){
            if (!res.contains(item)){
            res.add(new ArrayList<Integer>(item));
            return;
            }
        }

        for(int i = 0; i<num.length;i++){
            if(!visited[i]){
                item.add(num[i]);
                visited[i]=true;
                permutation_helper(num,res,item,visited);
                item.remove(item.size()-1);
                visited[i]=false;
            }
        }
    }
    public static void main(String[] args) {
        leetcode46 leetcode46 = new leetcode46();
        int[] a = {-1,2,3};
        System.out.println(leetcode46.permute(a));
    }
}
